1. Field of the Invention
This invention relates generally to multithreaded computer systems and, more specifically, to a system and method for improving the operation of transactional memory systems.
2. Description of the Related Art
Due to the complexity and energy concerns of modern processors, traditional approaches to boosting CPU performance have become difficult and ineffective. Instead of attempting to drive up clock speeds, computer architects are increasingly turning to multi-threading techniques such as symmetric multi-threading or multi-core architectures. In order to leverage these new architectures, software engineers must write applications that execute using multiple concurrent threads of execution. Unfortunately, correct multi-threaded programming is notoriously difficult using traditional language constructs.
Shared-memory systems allow multiple threads to access and operate on the same memory locations. Traditional constructs, such as mutual exclusion and locks may be used by a thread to ensure correctness by allowing the thread to exclude all other threads from accessing a given shared memory location or shared function while the thread is executing a critical section of code. While a lock is being held, all other threads wishing to execute a critical section dependant on that lock must await the lock's release and acquire it before proceeding. While various attempts to execute a given critical section may depend on the acquisition of multiple locks and/or dynamically determined locks (e.g., locks dependent on instance-specific shared data), the term critical section, as used herein, may generally refer to a code path or a set of program instructions protected by a given lock.
The pitfalls of locking constructs are numerous and well known. They include dead-lock, race conditions, priority inversions, software complexity, and performance limitations. Locking is a heavy-handed approach to concurrency control.
Alternatively, it may be possible to increase parallelism by allowing multiple threads to concurrently execute critical sections that depend on common locks. This may increase performance and mitigate or eliminate many of the pitfalls normally associated with traditional locking mechanisms. However, such interleaved executions are not guaranteed to be correct.
Transactional memory is a mechanism that can be leveraged to enable multiple threads to execute critical sections dependant on the same lock, concurrently and correctly. Transactional memory allows a thread to execute a series of instructions as a transaction, that is, either completely and atomically or not at all. The instructions comprising a transaction are executed and then either “committed”, allowing the aggregate effect to be seen by all other threads, or “aborted”, allowing no effect to be seen. A transaction that has committed successfully may be said to have “succeeded”. Transactional lock-elision (TLE) is a technique that allows threads to execute critical sections dependant on the same lock or locks concurrently and transactionally without necessarily acquiring the corresponding lock. It provides identical semantics to traditional mutual exclusion but allows threads to execute critical sections as transactions that can be aborted if conflicts occur. Under TLE, instead of acquiring a lock, a thread may attempt to execute the critical section as a transaction, and simply abort if a conflict occurs with another thread before the transaction can be committed. This may be referred to as “transactionally eliding” a lock. The lock elision is successful if the thread successfully executes and commits a critical section dependant on that lock. Aborted transactions may be retried by the thread later.
In some TLE implementations, in response to repeated aborts, insufficient system resources, or other conditions, threads may revert to executing critical sections using mutual exclusion (e.g., by acquiring and/or holding one or more locks) rather than in a transactional mode (e.g., transactionally eliding such locks). If a thread acquires a lock, then no other threads may concurrently elide that lock. Therefore, mutually excluding threads may cause other threads to also execute using mutual exclusion rather than transactionally. As more threads revert to mutual exclusion, the likelihood grows that still more threads dependent on the same lock(s) will likewise revert to mutual exclusion rather than executing in a transactional mode. The net effect is that transactional mode execution of some critical sections may cease altogether until contention abates. This phenomenon may be detrimental to system performance and is referred to herein as the lemming effect.